function [FrontNo, MaxFNo] = NDSort(varargin)
% This code is copy from PlatEMO(https://github.com/BIMK/PlatEMO).

%NDSort - Perform non-dominated sorting by using efficient non-dominated
%sort.
%
%   FrontNo = NDSort(F,s) performs non-dominated sorting on F, where F is
%   the matrix of objective values of a set of solutions, and s is the
%   number of solutions to be sorted at least. FrontNo(i) denotes the front
%   number of the i-th solution. The solutions have not been sorted are
%   assigned a front number of inf.
%
%   FrontNo = NDSort(F,C,s) performs non-dominated sorting based on
%   constrained domination, where C is the matrix of constraint violations
%   of solutions. In this case, feasible solutions always dominate
%   infeasible solutions, and one infeasible solution dominates another
%   infeasible solution if the former has a smaller overall constraint
%   violation than the latter.
%
%   In particular, s = 1 indicates finding only the first non-dominated
%   front, s = size(F,1)/2 indicates sorting only half the population
%   (which is often used in algorithms), and s = inf indicates sorting the
%   whole population.
%
%   [FrontNo,K] = NDSort(...) also returns the maximum front number besides
%   inf.
%
%   Example:
%       [FrontNo,MaxFNo] = NDSort(PopObj,1)
%       [FrontNo,MaxFNo] = NDSort(PopObj,PopCon,inf)

%------------------------------- Reference --------------------------------
% [1] X. Zhang, Y. Tian, R. Cheng, and Y. Jin, An efficient approach to
% nondominated sorting for evolutionary multiobjective optimization, IEEE
% Transactions on Evolutionary Computation, 2015, 19(2): 201-213.
% [2] X. Zhang, Y. Tian, R. Cheng, and Y. Jin, A decision variable
% clustering based evolutionary algorithm for large-scale many-objective
% optimization, IEEE Transactions on Evolutionary Computation, 2018, 22(1):
% 97-112.
%------------------------------- Copyright --------------------------------
% Copyright (c) 2022 BIMK Group. You are free to use the PlatEMO for
% research purposes. All publications which use this platform or any code
% in the platform should acknowledge the use of "PlatEMO" and reference "Ye
% Tian, Ran Cheng, Xingyi Zhang, and Yaochu Jin, PlatEMO: A MATLAB platform
% for evolutionary multi-objective optimization [educational forum], IEEE
% Computational Intelligence Magazine, 2017, 12(4): 73-87".
%--------------------------------------------------------------------------

PopObj = varargin{1};
[N, M] = size(PopObj);
if nargin == 2
    nSort = varargin{2};
else
    PopCon = varargin{2};
    nSort = varargin{3};
    Infeasible = any(PopCon > 0, 2);
    PopObj(Infeasible, :) = repmat(max(PopObj, [], 1), sum(Infeasible), 1) + repmat(sum(max(0, PopCon(Infeasible, :)), 2), 1, M);
end
if M < 3 || N < 500
    % Use efficient non-dominated sort with sequential search (ENS-SS)
    [FrontNo, MaxFNo] = ENS_SS(PopObj, nSort);
else
    % Use tree-based efficient non-dominated sort (T-ENS)
    [FrontNo, MaxFNo] = T_ENS(PopObj, nSort);
end
end

function [FrontNo, MaxFNo] = ENS_SS(PopObj, nSort)
[PopObj, ~, Loc] = unique(PopObj, 'rows');
Table = hist(Loc, 1:max(Loc));
[N, M] = size(PopObj);
FrontNo = inf(1, N);
MaxFNo = 0;
while sum(Table(FrontNo < inf)) < min(nSort, length(Loc))
    MaxFNo = MaxFNo + 1;
    for i = 1:N
        if FrontNo(i) == inf
            Dominated = false;
            for j = i - 1:-1:1
                if FrontNo(j) == MaxFNo
                    m = 2;
                    while m <= M && PopObj(i, m) >= PopObj(j, m)
                        m = m + 1;
                    end
                    Dominated = m > M;
                    if Dominated || M == 2
                        break;
                    end
                end
            end
            if ~Dominated
                FrontNo(i) = MaxFNo;
            end
        end
    end
end
FrontNo = FrontNo(:, Loc);
end

function [FrontNo, MaxFNo] = T_ENS(PopObj, nSort)
[PopObj, ~, Loc] = unique(PopObj, 'rows');
Table = hist(Loc, 1:max(Loc));
[N, M] = size(PopObj);
FrontNo = inf(1, N);
MaxFNo = 0;
Forest = zeros(1, N);
Children = zeros(N, M - 1);
LeftChild = zeros(1, N) + M;
Father = zeros(1, N);
Brother = zeros(1, N) + M;
[~, ORank] = sort(PopObj(:, 2:M), 2, 'descend');
ORank = ORank + 1;
while sum(Table(FrontNo < inf)) < min(nSort, length(Loc))
    MaxFNo = MaxFNo + 1;
    root = find(FrontNo == inf, 1);
    Forest(MaxFNo) = root;
    FrontNo(root) = MaxFNo;
    for p = 1:N
        if FrontNo(p) == inf
            Pruning = zeros(1, N);
            q = Forest(MaxFNo);
            while true
                m = 1;
                while m < M && PopObj(p, ORank(q, m)) >= PopObj(q, ORank(q, m))
                    m = m + 1;
                end
                if m == M
                    break;
                else
                    Pruning(q) = m;
                    if LeftChild(q) <= Pruning(q)
                        q = Children(q, LeftChild(q));
                    else
                        while Father(q) && Brother(q) > Pruning(Father(q))
                            q = Father(q);
                        end
                        if Father(q)
                            q = Children(Father(q), Brother(q));
                        else
                            break;
                        end
                    end
                end
            end
            if m < M
                FrontNo(p) = MaxFNo;
                q = Forest(MaxFNo);
                while Children(q, Pruning(q))
                    q = Children(q, Pruning(q));
                end
                Children(q, Pruning(q)) = p;
                Father(p) = q;
                if LeftChild(q) > Pruning(q)
                    Brother(p) = LeftChild(q);
                    LeftChild(q) = Pruning(q);
                else
                    bro = Children(q, LeftChild(q));
                    while Brother(bro) < Pruning(q)
                        bro = Children(q, Brother(bro));
                    end
                    Brother(p) = Brother(bro);
                    Brother(bro) = Pruning(q);
                end
            end
        end
    end
end
FrontNo = FrontNo(:, Loc);
end
